//Given a string s, partition s such that every substring of the partition is a 
//palindrome. 
//
// Return the minimum cuts needed for a palindrome partitioning of s. 
//
// 
// Example 1: 
//
// 
//Input: s = "aab"
//Output: 1
//Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 
//cut.
// 
//
// Example 2: 
//
// 
//Input: s = "a"
//Output: 0
// 
//
// Example 3: 
//
// 
//Input: s = "ab"
//Output: 1
// 
//
// 
// Constraints: 
//
// 
// 1 <= s.length <= 2000 
// s consists of lower-case English letters only. 
// 
// Related Topics 字符串 动态规划 
// 👍 478 👎 0

package leetcode.editor.cn;

import java.util.Arrays;

 class P132PalindromePartitioningIi {
    public static void main(String[] args) {
        Solution solution = new P132PalindromePartitioningIi().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int minCut(String s) {
            int n = s.length();
            boolean[][] g = new boolean[n][n];
            for (int i = 0; i < n; ++i) {
                Arrays.fill(g[i], true);
            }

            for (int i = n - 1; i >= 0; --i) {
                for (int j = i + 1; j < n; ++j) {
                    g[i][j] = s.charAt(i) == s.charAt(j) && g[i + 1][j - 1];
                }
            }

            int[] f = new int[n];
            Arrays.fill(f, Integer.MAX_VALUE);
            for (int i = 0; i < n; ++i) {
                if (g[0][i]) {
                    f[i] = 0;
                } else {
                    for (int j = 0; j < i; ++j) {
                        if (g[j + 1][i]) {
                            f[i] = Math.min(f[i], f[j] + 1);
                        }
                    }
                }
            }

            return f[n - 1];
        }
    }

//runtime:38 ms
//memory:39.5 MB

//leetcode submit region end(Prohibit modification and deletion)

}